package com.gavin.algorithm.sort;

import java.util.Arrays;

/**
 * 堆排序
 * @author Administrator
 *
 */
public class HeapSort {

	public static void main(String[] args) {
		int[] a = { 0,26, 53, 67, 48, 57, 13, 48, 32, 60, 50 };
		heapSort(a);
		System.out.println(Arrays.toString(a));

	}
	
	
	private static void heapSort(int[] array) {
		int i,j;
		
		int length=array.length-1;
		//初始化大顶堆
		for(i=length/2;i>0;i--) {
			heapAdjust(array,i,length);
		}
		
		for(j=length;j>1;j--) {
			swap(array,j,1); //交换堆顶和堆底元素
			heapAdjust(array,1,j-1); //重新调整堆
		}
	}
	
	private static void heapAdjust(int[] array,int index,int length) {
		
		int i,temp=array[index];
		for(i=index*2;i<=length;i*=2) {
			if(i<length&&array[i]<array[i+1]) {
				i++;
			}
			if(temp>=array[i]) {
				break;
			}
			array[index]=array[i];
			index=i;
		}
		array[index]=temp;
	}
	
	private static void swap(int[] array,int i,int j) {
		int temp=array[i];
		array[i]=array[j];
		array[j]=temp;
	}
}
